package com.github.hgkmail.hello.leetcode101.collection;

import java.util.*;

public class TestCollection {
    public void testTreeMap() {
        //tree map默认[升序]排序，实现是红黑树，作为一种查找树，它擅长范围查找
        //插入、删除、查找的时间效率是O(logN)
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        treeMap.put(2,1);
        treeMap.put(3,1);
        treeMap.put(10,1);
        treeMap.put(5,1);
        treeMap.put(20,1);
        treeMap.put(1,1);

        //SortedMap接口部分
        //按指定范围获取key，subMap(K fromKey, K toKey)
        System.out.println(treeMap.subMap(1,5)); //{1=1, 2=1, 3=1}，可以看出是左闭右开

        //headMap(K toKey)，获取比toKey小的key，head——在前面，前面就是小
        System.out.println(treeMap.headMap(10));

        //tailMap(K fromKey)，获取大于或等于fromKey的key，tail——在后面，后面就是大
        System.out.println(treeMap.tailMap(10));

        //升序
        System.out.println(treeMap.firstKey()); //最小的key
        System.out.println(treeMap.firstEntry());
        System.out.println(treeMap.lastKey()); //最大的key
        System.out.println(treeMap.lastEntry());
        System.out.println(treeMap.keySet()); //按升序返回key

        //NavigableMap接口部分，用来查询最接近的key（closest）
        //floorKey(K key)，返回小于或等于key的最大的键，floor——地面，地面就是小于等于
        System.out.println(treeMap.floorKey(8));
        System.out.println(treeMap.floorEntry(10));

        //lowerKey(K key)，返回小于key的最大的键，lower——底部，底部就是严格小于（注意C++中lower_bound是大于等于，不一样）
        System.out.println(treeMap.lowerKey(8));
        System.out.println(treeMap.lowerEntry(10));

        //ceilingKey(K key)，返回大于或等于key的最大的键，ceiling——天花板，天花板就是大于等于
        System.out.println(treeMap.ceilingKey(8));
        System.out.println(treeMap.ceilingEntry(10));

        //higherKey(K key)，返回大于key的最大的键，higher——更高，更高就是严格大于
        System.out.println(treeMap.higherKey(8));
        System.out.println(treeMap.higherKey(10));

        //改为降序
        System.out.println(treeMap.descendingMap());
    }

    public void testTreeSet() {
        //tree set默认升序，内部通过一个tree map实现，可以看成没有value的tree map。
        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(2);
        treeSet.add(3);
        treeSet.add(10);
        treeSet.add(5);
        treeSet.add(20);
        treeSet.add(1);

        //升序
        System.out.println(treeSet);

        System.out.println(treeSet.first());
        System.out.println(treeSet.last());
        System.out.println(treeSet.subSet(3,10)); //左闭右开
        System.out.println(treeSet.headSet(10)); //＜key
        System.out.println(treeSet.tailSet(10)); //≥key
        System.out.println(treeSet.floor(8));
        System.out.println(treeSet.lower(10));
        System.out.println(treeSet.ceiling(8));
        System.out.println(treeSet.higher(10));
        System.out.println(treeSet.descendingSet());
    }

    public void testRandom() {
        Random random = new Random(); //以系统自身时间为种子数
        //随机生成一个整数，范围是int类型的取值范围：Integer.MIN_VALUE ~ Integer.MAX_VALUE
        System.out.println(random.nextInt());
        // [0, bound) 左闭右开
        System.out.println(random.nextInt(3));
        //[0.0, 1.0] 左闭右闭
        System.out.println(random.nextDouble());
        //[0.0, 5.0] 左闭右闭
        System.out.println(random.nextDouble()*5);
    }

    //hashmap + 双向链表
    //双向链表可以按插入顺序，也可以按访问顺序，新的在链表尾部，旧的在链表头部
    public void testLinkedHashMap() {
        //默认insertion order，双向链表按插入顺序
        LinkedHashMap<Integer, Integer> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put(2,1);
        linkedHashMap.put(3,1);
        linkedHashMap.put(10,1);
        linkedHashMap.put(5,1);
        //先移除再插入才能改变顺序
        //不移除直接重复插入不改变顺序
        linkedHashMap.remove(10);
        linkedHashMap.put(10, 1);
        System.out.println(linkedHashMap.keySet());

        //access order，双向链表按访问顺序，可以用于实现LRUCache
        LinkedHashMap<Integer, Integer> linkedHashMap2 = new LinkedHashMap<>(16, .75f, true);
        linkedHashMap2.put(2,1);
        linkedHashMap2.put(3,1);
        linkedHashMap2.put(10,1);
        linkedHashMap2.put(5,1);
        linkedHashMap2.get(10);
        linkedHashMap2.get(3);
        System.out.println(linkedHashMap2.keySet()); // [2, 5, 10, 3]
    }

    public void testLinkedHashSet() {
        //hashset+双向链表，按插入顺序
        LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add(2);
        linkedHashSet.add(5);
        linkedHashSet.add(3);
        linkedHashSet.add(10);
        linkedHashSet.remove(3);
        linkedHashSet.add(3);
        System.out.println(linkedHashSet);
    }

    public void testIdentityHashMap() {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(1,1);
        hashMap.put(2,2);
        hashMap.put(2,3);
//        System.out.println(hashMap);

        //IdentityHashMap是一个特殊的Map，它基于引用相等性(reference equality)，key允许重复、null值
        //要发挥IdentityHashMap的特性，存放key时要new一个对象
        Map<Integer, Integer> identityHashMap = new IdentityHashMap<>();
        identityHashMap.put(new Integer(1),1);
        identityHashMap.put(new Integer(2),2);
        identityHashMap.put(new Integer(2),3);
        identityHashMap.put(null,3);
        System.out.println(identityHashMap);
    }

    public static void main(String[] args) {
        TestCollection test = new TestCollection();
//        test.testTreeMap();
//        test.testTreeSet();
//        test.testRandom();
//        test.testLinkedHashMap();
//        test.testLinkedHashSet();
        test.testIdentityHashMap();
    }

}
